package com.datastructures2.tree2;

/**
 * 堆(优先队列)
 *
 * @author MaoLin Wang
 * @date 2020/2/1611:26
 */
public class BinaryHeap<T extends Comparable<? super T>> {
    private static final int DEFAULT_CAPACITY = 10;
    private int currentSize;
    private T[] array;

    public BinaryHeap() {
        this(DEFAULT_CAPACITY);
    }

    public BinaryHeap(int capacity) {
        this.currentSize = 0;
        array = (T[]) new Comparable[capacity + 1];
    }

    public BinaryHeap(T[] array) {
        currentSize = array.length;
        this.array = (T[]) new Comparable[(currentSize + 2) * 11 / 10];
        int i = 1;
        for (T arr : array) {
            array[i++] = arr;
        }
        buildHead();
    }

    private void buildHead() {
        for (int i = currentSize/2; i >0 ; i--) {
            percolateDown(i);
        }
    }


    private void enlargeArray(int newSize) {
        T[] old = array;
        array = (T[]) new Comparable[newSize];
        for (int i = 0; i < old.length; i++) {
            array[i] = old[i];
        }
    }

    /**
     * 先建立一个空位置 hole,上滤直到找到满足堆序的位置，将x插入到该位置
     * array[0]暂存待插入元素x
     * @param x
     */
    public void insert(T x) {
        if (currentSize == array.length - 1) {
            enlargeArray(array.length * 2 + 1);
        }
        int hole=++currentSize;
        array[0]=x;
        percolateUp(hole,array[0]);
    }


    /**
     * 上滤
     * @param hole
     */
    private void percolateUp(int hole,T x){
        for ( ;  x.compareTo(array[hole/2])<0 ;hole /= 2) {
            array[hole]=array[hole/2];
        }
        array[hole]=x;
    }

    /**
     * 删除最小元素，下滤
     * 1.找到最小元素，移除（currentSize--,并将最后一个元素放在最小元素位置）
     * 2.对该元素进行下滤
     * @return
     */
    public T deleteMin(){
        if (isEmpty()){
            System.out.println("堆为空");
        }
        T min = findMin();
        array[1]=array[currentSize--];
        percolateDown(1);
        return min;

    }

    /**
     * 从hole开始下滤
     * @param hole
     */
    private void percolateDown(int hole) {
        int child;
        T temp = array[hole];
        for ( ; hole*2<=currentSize ;hole=child ) {
            child=hole*2;
            if (child!=currentSize&& //保证偶数个节点的情况下，最后一个hole只有一个左儿子
                array[child+1].compareTo(array[child])<0){
                child++;
            }
            if (array[child].compareTo(temp)<0){
                array[hole]=array[child];
            }else
                break;
        }
        array[hole]=temp;
    }


    public T findMin(){
        if (isEmpty()){
            System.out.println("堆为空");
        }
        return array[1];
    }
    public void print(){
        for (int i = 1; i <currentSize ; i++) {
            System.out.println(array[i]);
        }
    }

    public boolean isEmpty() {
        return currentSize==0;
    }
    // Test program
    public static void main( String [ ] args )
    {
        BinaryHeap<Integer> heap = new BinaryHeap<>();
        heap.insert(13);
        heap.insert(14);
        heap.insert(16);
        heap.insert(19);
        heap.insert(21);
        heap.insert(19);
        heap.insert(68);
        heap.insert(65);
        heap.insert(26);
        heap.insert(32);
        heap.insert(31);
        System.out.println("-----");
        while (!heap.isEmpty()){
            //依此出队
            System.out.println(heap.deleteMin());
        }

    }
}
